package cn.zzf.leetcode;

/**
 * <b>5. 最长回文子串</b>
 * 给你一个字符串 s，找到 s 中最长的 回文 子串。<br/>
 * <p>
 * 示例 1：<br/>
 * 输入：s = "babad"<br/>
 * 输出："bab"<br/>
 * 解释："aba" 同样是符合题意的答案。<br/>
 * <p>
 * 示例 2：<br/>
 * 输入：s = "cbbd"<br/>
 * 输出："bb"<br/>
 * <p>
 * 提示：<br/>
 * 1 <= s.length <= 1000<br/>
 * s 仅由数字和英文字母组成<br/>
 *
 * @author zzf
 * @date 2025-05-27 17:47
 */
public class T0005_LongestPalindrome {

    /**
     * 5ms
     * 核心思路为中心扩散法，比较从每个字符为中心扩散的长度，记录当时最大长度以及开始索引位。<br/>
     * <p>
     * 需要考虑两种情况： BAAB和BAB，极端情况下为：AAAAAAAA<br/>
     * 因此在扩散时同时判断两种情况下的扩散长度。<br/>
     * 设字符串char数组为s[], 当前索引位为 i<br/>
     * 要判断 s[i] == s[i + 1] 以及 s[i - 1] == s[i + 1]<br/>
     *
     *
     * <pre>{@code
     *  i
     *  1 2 2 1
     *  ↑ ↑
     *
     *    i
     *  1 2 2 1
     *  ↑   ↑
     *
     *    i
     *  1 2 2 1
     *    ↑ ↑
     *
     *    i
     *  1 2 2 1
     *  ↑     ↑
     * }</pre>
     *
     * @param s
     * @return
     * @author zzf
     * @date 2025-05-29 08:47
     */
    public static String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        // 当前长度，最大长度(默认给1)，最大长度时的左索引位
        int currentLength, maxLength = 1, maxLeft = 0;
        char[] ca = s.toCharArray();
        int length = s.length();
        // 记录当前扩散到的左右索引位
        int left, right;

        // 最后一个没必要判断，i - 1时会判断。
        for (int i = 0; i < ca.length - 1; i++) {
            //        i
            // 比较 xx A A xx情况
            //        ↑ ↑

            // 重置值
            left = i;
            right = i + 1;
            currentLength = 0;
            if (ca[left] == ca[right]) {
                // ... A A ... = 2
                currentLength += 2;
                // 开始扩散，两侧索引往外推，直至值不一致或到头为止
                while (left > 0 && right < length - 1) {
                    left--;
                    right++;
                    if (ca[left] != ca[right]) {
                        // 加回来是因为此时不相等，所以真正开始回文的索引位为后一位
                        left++;
                        break;
                    }
                    currentLength += 2;
                }
                // 记录结果
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                    maxLeft = left;
                }
            }
            if (i > 0) {
                //          i
                // 比较 xx A X A xx情况
                //        ↑   ↑

                // 重置值
                left = i - 1;
                right = i + 1;
                currentLength = 0;
                if (ca[left] == ca[right]) {
                    // A X A = 3
                    currentLength += 3;
                    // 开始扩散，两侧索引往外推，直至值不一致或到头为止
                    while (left > 0 && right < length - 1) {
                        left--;
                        right++;
                        if (ca[left] != ca[right]) {
                            // 加回来是因为此时不相等，所以真正开始回文的索引位为后一位
                            left++;
                            break;
                        }
                        currentLength += 2;
                    }
                    // 记录结果
                    if (currentLength > maxLength) {
                        maxLength = currentLength;
                        maxLeft = left;
                    }
                }
            }
        }
        return s.substring(maxLeft, maxLeft + maxLength);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abb"));
        ;
    }
}
